
#include "txml.h"
#include "tclib.h"

//an in-place, streaming, non-destructive xml parser
//no entities, no DTD, no validation.
//reasonable namespacing support.
//some utf8 compatibility (properly skips any BOM, output may contain utf8 words)
//some utf16 compatibility (detects BOM and raises an error)

//assumes all markup is in the basic 7-bit ascii character code space

//does not replace special xml expressions, eg &amp (todo: provide library code to do
//destructively but in-place)

namespace TXML
{
	//guts of the parser, this makes it all work. cannot search for a utf8 word, or any extended ascii (8 bit) code.
	//(ie. should only be used to detect markup, not character data).
	String FindChar(char c, unsigned char nth, bool bIgnoreQuoted, bool bUtf8, const String& str)
	{
		int n = 0;
		const char* p = str.begin();
		int quote = 0;

		while(*p && p!=str.end())
		{	
			if(bIgnoreQuoted)
				if(*p == '"')
					quote = (quote == 0) ? 1 : 0; //flip quote, if ignoring quoted text during scan

			if(quote == 0 && *p == c)
			{
				++n;
				if(n==nth)
					return String(p, p+1);
			}
			
			//utf8 - anything with the high bit set is multi-byte. unfortunately,
			//any extended ascii set may also trip this so have to treat separately.
			if(bUtf8)
				do{ ++p; }while(*p && (*p & 0x80));
			else
				++p;
		}
		return String(NULL, NULL);
	}

	String FindChar(char c, bool bUtf8, const String& str)
	{
		return FindChar(c, 1, true, bUtf8, str);
	}

	bool IsEmpty(const String& elem)
	{
		//scan back, look for closing slash
		return *(elem.end()-2) == '/';
	}

	bool IsClosing(const String& elem)
	{
		return *(elem.begin()+1) == '/';
	}

	bool IsComment(const String& elem)
	{
		return *(elem.begin()+1) == '!';
	}

	bool IsMeta(const String& elem)
	{
		return *(elem.begin()+1) == '?' && *(elem.end()-2) == '?';
	}

	//find the fully qualified name of an element, which includes its namespace
	String FQElemName(const String& elem, bool bUtf8)
	{
		String lelem;

		//skip the / if its a closing element
		if(IsClosing(elem))
			lelem = String(elem.begin()+2, elem.end());
		else
			lelem = String(elem.begin()+1, elem.end());

		//attributes present
		String end = FindChar(' ', bUtf8, lelem);

		if(!end.length())
			end = FindChar('/', bUtf8, lelem);
				
		if(!end.length())
			end = FindChar('>', bUtf8, lelem);
				
		if(end.length())
			return String(lelem.begin(), end.begin());
		else	
			return String();
	}

	//split a element name down into a name/namespace pair
	void CrackNamespace(const String& fqElemName, bool bUtf8, String& name, String& ns)
	{
		//find the : marker
		String split = FindChar(':', bUtf8, fqElemName);
		if(split.empty())
		{
			//no namespace
			ns = String();
			name = fqElemName;
		}
		else
		{
			//found a namespace
			ns = String(fqElemName.begin(), split.begin());
			name = String(split.begin()+1, fqElemName.end());
		}
	}

	String FirstElement(String& doc, bool bUtf8)
	{
		String out(NULL, NULL);
		
		String begin = FindChar('<', bUtf8, doc);
		String end = FindChar('>', bUtf8, doc);
		
		if(begin.length() && end.length())
			return String(begin.begin(), end.end());
		else return String(NULL,NULL);
	}

	String ReduceElemToAttributes(const String& elem, bool bUtf8)
	{
		String start = FindChar(' ', bUtf8, elem);
		String end = FindChar('>', bUtf8, elem);

		if(!end.empty())
		{
			//try winding back for empty or PI elems
			char c = *(end.begin()-1);
			if( c == '/' || c == '?' )
				end = String(end.begin()-1, end.end()-1);
		}	
		
		return (!start.empty() && !end.empty()) ? String(start.begin(), end.begin()) : String(NULL, NULL);
	}

	static bool IsWhitespace(const char* p)
	{
		return (*p == ' ' || *p == '\t' || *p == '\n' || *p == '\r');
	}

	String TrimWS(const String& s)
	{
		const char* p = s.begin();
		while(p < s.end() && IsWhitespace(p))
			++p;

		//is the string now empty?
		if(p==s.end())
			return String(p,p);

		const char* q = s.end()-1;
		while(q > p && IsWhitespace(q) )
			--q;

		return String(p,q+1);
	}
	
	void Parser::ProcessAttribute(const String& attr, bool bUtf8, Consumer* pConsumer)
	{
		//partition based on =, eat ws, check it looks cool, crack ns and so on
		String a = TrimWS(attr);

		String eq = FindChar('=', 1, false, bUtf8, a);

		String fqname(a.begin(), eq.begin());
		fqname = TrimWS(fqname);

		String name, ns;
		CrackNamespace(fqname, bUtf8, name, ns);

		String quote = FindChar('"', 1, false, bUtf8, String(eq.begin(), a.end()));

		if(!quote.empty())
		{
			String value(quote.end(), a.end());
			//identify xml namespaces separately from normal attributes
			if(ns.equals("xmlns"))
			{
				pConsumer->NamespaceDeclaration(name, value);
			}
			else
			{
				pConsumer->Attribute(name, ns, value);
			}
		}
		else
		{
			pConsumer->AttributeError(a);
		}
	}

	void Parser::ProcessAttributes(const String& elem, bool bUtf8, Consumer* pConsumer)
	{
		//narrow down the range, exclude the element (fq) name and the end bits
		String attribs = ReduceElemToAttributes(elem, bUtf8);
		
		if(!attribs.empty())
		{
			String curr = attribs;

			//use quotes and ='s to do the parse
			while(!curr.empty())
			{
				String quote = FindChar('"', 2, false, bUtf8, curr);
				ProcessAttribute( String(curr.begin(), quote.begin()), bUtf8, pConsumer );

				if(quote.end() < attribs.end())
					curr = String(quote.end(), attribs.end());
				else
					return; //fin.
			}
		}
	}

	//consumer for the <?xml ?> node, checks the nodes contents are acceptable.
	class XmlPIConsumer : public Consumer
	{
	public:
		XmlPIConsumer() :
			mbEncodingOK(false)
			, mbVersionOK(false)
		{		}

		String mXmlVersion;
		String mEncoding;

		bool mbEncodingOK;
		bool mbVersionOK;
		
		void Attribute(const String& name, const String& ns, const String& value)
		{
			if(name.equalsi("version"))
			{
				mXmlVersion = value;
			}
			else if(name.equalsi("encoding"))
			{
				mEncoding = value;
			}
		}

		bool IsValid()
		{
			//version should be 1.something
			//and the encoding should be something we can manage, definitely not wide-character
			//(the idea is, that we should be fine with utf8 or any extended ascii).

			mbVersionOK = true;
			if(!mXmlVersion.empty())
			{
				mbVersionOK = false;

				if( mXmlVersion.length() > 1
					&& *mXmlVersion.begin() == '1'
					&& *(mXmlVersion.begin()+1) == '.' )
				{
					mbVersionOK = true;
				}
			}

			//currently just blacklisting the common wide-char encodings.
			//a more secure way around this, would be to whitelist anything that is tested as OK by user of code.
			mbEncodingOK = true;
			
			static const char* excludedEncodings[] = {"UTF-16", "UTF-16BE", "UTF-16LE", "UTF-32", "UTF-32BE", "UTF-32LE", "ISO-10646-UCS-2", "ISO-10646-UCS-4"};
			static const size_t numEncodings = sizeof(excludedEncodings)/sizeof(const char*);
			for(size_t i = 0; i<numEncodings; ++i)
			{
				if(mEncoding.equalsi( excludedEncodings[i] ))
					mbEncodingOK = false;
			}

			return mbVersionOK && mbEncodingOK;
		}
	};
	
	void Parser::Parse(const char* pString, Consumer* pConsumer)
	{
		const char* start = pString;
		const char* end = pString + strlen(pString) + 1;
		String current(start, end);
		String elem(NULL, NULL);
		bool bUtf8 = false;

		//look for utf16 bom
		if(current.length() > 2)
		{
			const unsigned char* ubegin = reinterpret_cast<const unsigned char*>(current.begin());
			
			//can test for utf-16
			if( *ubegin == 0xFE && *(ubegin+1) == 0xFF )
			{
				//utf16 be
				pConsumer->ParseError(EPE_EncodingNotSupported);
				return;
			}
			else if(*ubegin == 0xFF && *(ubegin+1) == 0xFE )
			{
				//utf16 le
				pConsumer->ParseError(EPE_EncodingNotSupported);
				return;
			}
		}

		//and utf8 bom
		if(current.length() > 3)
		{
			const unsigned char* ubegin = reinterpret_cast<const unsigned char*>(current.begin());
			if( *ubegin == 0xEF
				&& *(ubegin+1) == 0xBB
				&& *(ubegin+2) == 0xBF )
			{
				//utf8, skip the bom
				current = String(current.begin()+3, current.end());
				bUtf8 = true;
			}
		}

		//set character data watermark and then loop all elements in the doc
		const char* pCharacterWatermark = current.begin();
		do
		{
			elem = FirstElement(current, bUtf8);
			if(elem.length() > 0)
			{
				//found an element, handle character text before processing
				//the element itself
				if( elem.begin() > pCharacterWatermark )
				{
					String chardata(pCharacterWatermark, elem.begin());
					chardata = TrimWS(chardata);
					if(!chardata.empty())
						pConsumer->ElementContents(chardata);
				}
				//move the character data watermark past the element, for next time around.
				pCharacterWatermark = elem.end();

				//now classify and process the element itself
				if( IsMeta(elem) )
				{
					String meta = FQElemName(elem, bUtf8);
					if(meta.equals("?xml"))
					{
						pConsumer->BeginElement(meta, String());
						//this node is important, so is parsed twice.

						//once internally, and if the output of that is acceptable
						//then again for the external consumer.
						
						//could parse once and multiplex the output, but this way yields
						//cleaner behaviour on errors (and feels less hacky).
						XmlPIConsumer c;
						ProcessAttributes(elem, bUtf8, &c);

						if(!c.IsValid())
						{
							if(!c.mbVersionOK)
								pConsumer->ParseError(EPE_VersionNotSupported);
							if(!c.mbEncodingOK)
								pConsumer->ParseError(EPE_EncodingNotSupported);

							return;
						}

						//if there was a BOM, then the encoding had better match.
						//otherwise, just go with the encoding attribute.
						if(!c.mEncoding.empty())
						{
							//check the bom and the encoding attr match
							bool bEncodingIsUtf8 = c.mEncoding.equalsi("UTF-8");
							if(bUtf8 && !bEncodingIsUtf8)
							{	//bom and encoding attr inconsistent, error
								pConsumer->ParseError(EPE_InconsistentEncoding);
								return;
							}

							//bom is either not present, or consistent with encoding tag
							//so just use the encoding tag.
							bUtf8 = bEncodingIsUtf8;
						}
						
						ProcessAttributes(elem, bUtf8, pConsumer);
						pConsumer->EndElement();
					}					
					
					//pass any other processing instructions straight through
				}
				else if( IsComment(elem) )
				{
					//dig out CDATA from comment markup
					//todo: be less sensitive about whitespace?
					const char kCDataStart[] = "<![CDATA[";
					size_t kCDataStartLen = sizeof(kCDataStart)/sizeof(char);

					const char kCDataEnd[] = "]]>";
					size_t kCDataEndLen = sizeof(kCDataEnd)/sizeof(char);

					if(elem.startswith(kCDataStart) && elem.endswith(kCDataEnd))
					{
						//strip the known constants off the string
						pConsumer->CData(String(elem.begin()+kCDataStartLen, elem.end()-kCDataEndLen));
					}
					//else random comment, ignore
				}
				else if( IsClosing(elem) )
				{
					//closing elem, check stack and drop - no attributes
					String name = FQElemName(elem, bUtf8);
					if(name.equals(mStack[mStackIdx-1]))
					{
						--mStackIdx; //cool, all good
						if(mStackIdx > 0)
							pConsumer->EndElement();
						else
							pConsumer->EndDocument();
					}
					else
					{
						pConsumer->ElementError(elem);
						return;
					}
				}
				else if( IsEmpty(elem) )
				{
					//empty elem, no change to stack but process attributes
					String name = FQElemName(elem, bUtf8);
					String localName, ns;

					CrackNamespace(name, bUtf8, localName, ns);
					pConsumer->BeginElement(localName, ns);

					ProcessAttributes(elem, bUtf8, pConsumer);

					pConsumer->EndElement();
				}
				else
				{
					//opening elem, push stack and process attributes
					String name = FQElemName(elem, bUtf8);
					if(name.length())
					{
						if(mStackIdx +1 == kMaxDepth)
						{
							pConsumer->ParseError(EPE_DocumentTooDeep);
							return;	//bail out, can't recover from this.
						}
						
						mStack[mStackIdx++]=name;
						
						String localName, ns;
						CrackNamespace(name, bUtf8, localName, ns);
						
						if(mStackIdx > 1)
							pConsumer->BeginElement(localName, ns);
						else
							pConsumer->BeginDocument(localName, ns);

						ProcessAttributes(elem, bUtf8, pConsumer);
					}
					else
					{
						pConsumer->ElementError(elem);
						return;
					}					
				}
			}

			current = String(elem.end(), current.end());
		}
		while(elem.length());		
	}
	
};